Blackwell's approachability theorem

Theorem

Let 𝒞⊂ℝ\mathscr{C} \subset \mathbb{R} be a convex and closed set, with support function w𝒞w_{\mathscr{C}}. Then 𝒞\mathscr{C} is approachable by ii if and only if for every λ∈ℝL\lambda \in \mathbb{R}^L there exists a mixed strategy qλ∈δ(Si)q_\lambda \in \delta(S^i) such that λ⋅v(qλ,s−i)≤w𝒞(λ),for all s−i∈S−i\lambda \cdot v (q_\lambda, s^{-i}) \leq w_\mathscr{C}(\lambda), \quad \text{for all } s^{-i} \in S^{-i}

References

  1. Hart S, Mas-Colell A. A Simple Adaptive Procedure Leading to Correlated Equilibrium. Econometrica, 2000; 68(5): 1127-1150.
  2. https://www.mit.edu/~gfarina/2021/15888f21_L04_blackwell_rm/L04_blackwell_rm.pdf
  3. https://ocw.mit.edu/courses/18-657-mathematics-of-machine-learning-fall-2015/b21de17384706de8db8078cd767d459e_MIT18_657F15_L22.pdf